package com.zhupf.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhupf
 * @date 2024年03月01日 10:56
 * @Description 763. 划分字母区间
 *
 *  给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
 *
 * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
 *
 * 返回一个表示每个字符串片段的长度的列表。
 *
 * 输入：s = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8]
 * 解释：
 * 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
 */
public class PartitionLabels {

    public static void main(String[] args) {
        List<Integer> list = partitionLabels("ababcbacadefegdehijhklij");
        System.out.println(list.toString());
    }

    public static List<Integer> partitionLabels(String s) {
        List<Integer> ans = new ArrayList<>();
        Map<Character,Integer> map = new HashMap<>();
        int len = s.length();
        for(int i = 0 ; i < len ; i++){
            map.put(s.charAt(i),i);
        }
        int idx = 0;
        int l = -1;
        int r = -1;
        while (idx < len){
            char charAt = s.charAt(idx);
            Integer integer = map.get(charAt);
            r = Math.max(r,integer);
            if(idx == r && integer == r){
                ans.add(r-l);
                l = idx;
            }
            idx++;
        }
        return ans;
    }

}
